{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Array Empty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #binary-indexed-tree #segment-tree #array #binary-search #ordered-set #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #树状数组 #线段树 #数组 #二分查找 #有序集合 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countOperationsToEmptyArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组清空"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个包含若干 <strong>互不相同</strong>&nbsp;整数的数组&nbsp;<code>nums</code>&nbsp;，你需要执行以下操作 <strong>直到</strong><strong>数组为空</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果数组中第一个元素是当前数组中的 <strong>最小值</strong>&nbsp;，则删除它。</li>\n",
    "\t<li>否则，将第一个元素移动到数组的 <strong>末尾</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回需要多少个操作使<em>&nbsp;</em><code>nums</code><em>&nbsp;</em>为空。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,4,-1]\n",
    "<b>输出：</b>5\n",
    "</pre>\n",
    "\n",
    "<table style=\"border: 2px solid black; border-collapse: collapse;\">\n",
    "\t<thead>\n",
    "\t\t<tr>\n",
    "\t\t\t<th style=\"border: 2px solid black; padding: 5px;\">Operation</th>\n",
    "\t\t\t<th style=\"border: 2px solid black; padding: 5px;\">Array</th>\n",
    "\t\t</tr>\n",
    "\t</thead>\n",
    "\t<tbody>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">1</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[4, -1, 3]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">2</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[-1, 3, 4]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">3</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[3, 4]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">4</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[4]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">5</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[]</td>\n",
    "\t\t</tr>\n",
    "\t</tbody>\n",
    "</table>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,4,3]\n",
    "<b>输出：</b>5\n",
    "</pre>\n",
    "\n",
    "<table style=\"border: 2px solid black; border-collapse: collapse;\">\n",
    "\t<thead>\n",
    "\t\t<tr>\n",
    "\t\t\t<th style=\"border: 2px solid black; padding: 5px;\">Operation</th>\n",
    "\t\t\t<th style=\"border: 2px solid black; padding: 5px;\">Array</th>\n",
    "\t\t</tr>\n",
    "\t</thead>\n",
    "\t<tbody>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">1</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[2, 4, 3]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">2</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[4, 3]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">3</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[3, 4]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">4</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[4]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">5</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[]</td>\n",
    "\t\t</tr>\n",
    "\t</tbody>\n",
    "</table>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3]\n",
    "<b>输出：</b>3\n",
    "</pre>\n",
    "\n",
    "<table style=\"border: 2px solid black; border-collapse: collapse;\">\n",
    "\t<thead>\n",
    "\t\t<tr>\n",
    "\t\t\t<th style=\"border: 2px solid black; padding: 5px;\">Operation</th>\n",
    "\t\t\t<th style=\"border: 2px solid black; padding: 5px;\">Array</th>\n",
    "\t\t</tr>\n",
    "\t</thead>\n",
    "\t<tbody>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">1</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[2, 3]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">2</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[3]</td>\n",
    "\t\t</tr>\n",
    "\t\t<tr>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">3</td>\n",
    "\t\t\t<td style=\"border: 2px solid black; padding: 5px;\">[]</td>\n",
    "\t\t</tr>\n",
    "\t</tbody>\n",
    "</table>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9&nbsp;</sup>&lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;中的元素 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-array-empty](https://leetcode.cn/problems/make-array-empty/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-array-empty](https://leetcode.cn/problems/make-array-empty/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,-1]', '[1,2,4,3]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id), 1):\n",
    "            if i < pre:\n",
    "                ans += n - k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self,nums:List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key = lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id) , 1):\n",
    "            if i < pre:\n",
    "                ans += n - k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k in range(1,n):\n",
    "            pre=id[k-1]\n",
    "            i=id[k]\n",
    "            if i<pre:\n",
    "                ans+=n-k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id), 1):\n",
    "            if i < pre:  # 必须多走一整圈\n",
    "                ans += n - k  # 减去前面删除的元素个数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self,nums:List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key = lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id) , 1):\n",
    "            if i < pre:\n",
    "                ans += n - k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        \n",
    "        idx = sorted(range(N), key=lambda x: nums[x])\n",
    "        \n",
    "        res = N\n",
    "        \n",
    "        for i in range(N - 1):\n",
    "            if idx[i] > idx[i + 1]:\n",
    "                res += N - i - 1\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self,nums:List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key = lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id) , 1):\n",
    "            if i < pre:\n",
    "                ans += n - k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id), 1):\n",
    "            if i < pre:  # 必须多走一整圈\n",
    "                ans += n - k  # 减去前面删除的元素个数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self,nums:List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key = lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id) , 1):\n",
    "            if i < pre:\n",
    "                ans += n - k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id), 1):\n",
    "            if i < pre:  # 必须多走一整圈\n",
    "                ans += n - k  # 减去前面删除的元素个数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans=n=len(nums)\n",
    "        id=sorted(range(n),key=lambda x:nums[x])\n",
    "        for k,(pre,i) in enumerate(pairwise(id),1):\n",
    "            if i<pre:\n",
    "                ans+=n-k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        index=sorted(range(n),key=lambda x:nums[x])\n",
    "        for i in range(1,n):\n",
    "            if index[i-1]>index[i]:\n",
    "                ans+=n-i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id), 1):\n",
    "            if i < pre:\n",
    "                ans += n - k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        b = sorted(range(n), key = lambda i: nums[i])\n",
    "        pre, ans, bit = 1, n, BIT(n + 1)\n",
    "        for _, x in enumerate(b):\n",
    "            x += 1\n",
    "            # x to pre\n",
    "            if x >= pre:\n",
    "                ans += x - pre - bit.sum(pre, x-1) \n",
    "            else:\n",
    "                visited = bit.sum(pre, n) + bit.sum(1, x - 1)\n",
    "                moved = n - pre + 1 + x - 1\n",
    "                ans += moved - visited\n",
    "            bit.add(x)\n",
    "            pre = x\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tr = [0] * n\n",
    "        self.n = n\n",
    "    \n",
    "    def add(self, x):\n",
    "        while x < self.n:\n",
    "            self.tr[x] += 1\n",
    "            x += x & -x\n",
    "    \n",
    "    def query(self, x):\n",
    "        ans = 0\n",
    "        while x:\n",
    "            ans += self.tr[x]\n",
    "            x -= x & -x\n",
    "        return ans\n",
    "    \n",
    "    def sum(self, x, y):\n",
    "        return self.query(y) - self.query(x - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos = sorted(range(n), key=lambda x:nums[x])\n",
    "        ans = len(nums)\n",
    "        cur = 0\n",
    "        for i in range(1,n):\n",
    "            if pos[i]<pos[i-1]:\n",
    "                ans+=n-i\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import pairwise\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=n\n",
    "        order=sorted(range(n),key=lambda x:nums[x])\n",
    "        for k,(pre,i) in enumerate(pairwise(order),1):\n",
    "            if i<pre:\n",
    "                ans+=n-k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=n\n",
    "        order=sorted(range(n),key=lambda x:nums[x])\n",
    "        #print(order)\n",
    "        for k in range(1,n):\n",
    "            pre,now=order[k-1],order[k]\n",
    "            #print(pre,now,k)\n",
    "            if now<pre:\n",
    "                ans+=n-k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k in range(1,n):\n",
    "            pre=id[k-1]\n",
    "            i=id[k]\n",
    "            if i<pre:\n",
    "                ans+=n-k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id), 1):\n",
    "            if i < pre:  # 必须多走一整圈\n",
    "                ans += n - k  # 减去前面删除的元素个数\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "关键在于理解删除数字的影响-->免费走一步,删过多少数字，就是免费走多少步\n",
    "这样就不用对每次移动进行模拟\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans=n=len(nums)\n",
    "        ids=sorted(range(n),key=lambda x:nums[x])\n",
    "        #ids[0]就是最小元素所在的下标\n",
    "        pre_sum=0\n",
    "        for k in range(1,n):\n",
    "            if ids[k]<ids[k-1]:\n",
    "                ans+=n-k\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        for k in range(1,n):\n",
    "            pre=id[k-1]\n",
    "            i=id[k]\n",
    "            if i<pre:\n",
    "                ans+=n-k\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self,nums:List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key = lambda x: nums[x])\n",
    "        for k, (pre, i) in enumerate(pairwise(id)):\n",
    "            if i < pre:\n",
    "                ans += n - k-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, a: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        s=SortedList()\n",
    "        n=len(a)\n",
    "        b=sorted(range(n),key=lambda x:a[x])\n",
    "        ans=0\n",
    "        c=-1\n",
    "        for i in b:\n",
    "            # print(i,c,ans,s)\n",
    "            if i>c:\n",
    "                r=s.bisect_right(i)\n",
    "                l=s.bisect_right(c)\n",
    "                ans+=i-c-(r-l)\n",
    "            else:\n",
    "                l=s.bisect_right(c)\n",
    "                ans+=n-c-1-(len(s)-l)+i+1-s.bisect_right(i)\n",
    "            # print(ans)\n",
    "            s.add(i)\n",
    "            c=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        t = BIT(n + 1)\n",
    "        pre = 1\n",
    "        for k,i in enumerate(sorted(range(n), key = lambda i:nums[i])):\n",
    "            i += 1\n",
    "            if i >= pre:\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            t.inc(i)\n",
    "            pre = i\n",
    "        return ans\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * n\n",
    "    def inc(self, i:int) ->None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "    def sum(self, i:int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "    def query(self,left:int,right:int)->int:\n",
    "        return self.sum(right) - self.sum(left-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    \n",
    "    def inc(self, i):\n",
    "        while i<len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "    \n",
    "    def sum(self, i):\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= i & -i\n",
    "        return res\n",
    "    \n",
    "    def query(self, left, right):\n",
    "        return self.sum(right) - self.sum(left-1)\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        pre = 1\n",
    "        t = BIT(n+1)\n",
    "        ids = sorted(range(n), key=lambda i: nums[i])\n",
    "        for k, i in enumerate(ids):\n",
    "            i += 1\n",
    "            if pre <= i:\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:\n",
    "                ans += n - pre - t.query(pre, n) + i - t.query(1,i)\n",
    "            t.inc(i)\n",
    "            pre = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    \n",
    "    def inc(self, i):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i&-i\n",
    "    \n",
    "    def sum(self, i):\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= i&-i\n",
    "        return res\n",
    "    \n",
    "    def query(self, left, right):\n",
    "        return self.sum(right) - self.sum(left-1)\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bit = BIT(n+1)\n",
    "        sortnums = sorted(range(n), key=lambda x:nums[x])\n",
    "        pre = 1\n",
    "        res = n\n",
    "        for i in sortnums:\n",
    "            i += 1\n",
    "            if pre <= i:\n",
    "                res += i - pre - bit.query(pre, i)\n",
    "            else:\n",
    "                res += n - pre - bit.query(pre, n) + i - bit.query(1,i)\n",
    "            bit.inc(i)\n",
    "            pre = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "lowbit = lambda x : x & (-x)\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    \n",
    "    def update(self, i: int, k: int):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += lowbit(i)\n",
    "    \n",
    "    def sum(self, i):\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= lowbit(i)\n",
    "        return res\n",
    "    \n",
    "    def query(self, l, r):\n",
    "        return self.sum(r) - self.sum(l - 1)\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        tree = BIT(n + 1)\n",
    "        pre = 1\n",
    "        l = sorted(range(1, n+1), key=lambda i : nums[i - 1])\n",
    "        for i in l:\n",
    "            if i >= pre:\n",
    "                ans += i - pre - tree.query(pre, i)\n",
    "            else:\n",
    "                ans += (n - pre - tree.query(pre, n)) + (i - tree.query(1, i))\n",
    "            pre = i\n",
    "            tree.update(i, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.array = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, idx):\n",
    "        idx += 1 \n",
    "        while idx < len(self.array):\n",
    "            self.array[idx] += 1 \n",
    "            idx += idx & (- idx)\n",
    "    \n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        idx += 1 \n",
    "        while idx > 0:\n",
    "            res += self.array[idx]\n",
    "            idx -= idx & (- idx)\n",
    "        return res \n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        pre = - 1 \n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        bit = BIT(n)\n",
    "        for idx in sorted(range(n), key = lambda x: nums[x]):\n",
    "            if idx < pre:\n",
    "                res += n - 1 - pre \n",
    "                res -= bit.query(n - 1) - bit.query(pre)\n",
    "                pre = - 1\n",
    "            res += idx - pre \n",
    "            res -= bit.query(idx) - bit.query(pre)\n",
    "            bit.update(idx)\n",
    "            pre = idx \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        t = BIT(n+1)\n",
    "        ids = sorted(range(n), key=lambda i: nums[i])\n",
    "\n",
    "        ans = n\n",
    "        pre = 1\n",
    "        for k, i in enumerate(ids):\n",
    "            i += 1\n",
    "            if pre <= i:\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            pre = i\n",
    "            t.inc(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        l, res = sorted(list(range(len(nums))), key = lambda x: nums[x]), len(nums)\n",
    "        for i in range(1, len(l)):\n",
    "            if l[i] < l[i - 1]:\n",
    "                res += len(l) - i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        # 无重复元素的数组nums， 如果当前第一个元素为nums的最小值，删除，否则移动到数组末尾，多少次操作可以使nums清空\n",
    "        # \n",
    "        ans = n = len(nums)  # 先把 n 计入答案\n",
    "        t = BIT(n + 1)  # 下标从 1 开始\n",
    "        pre = 1  # 上一个最小值的位置，初始为 1\n",
    "        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):\n",
    "            i += 1  # 下标从 1 开始\n",
    "            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            t.inc(i)  # 删除 i\n",
    "            pre = i\n",
    "        return ans\n",
    "\n",
    "# 树状数组模板\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)  # 先把 n 计入答案\n",
    "        t = BIT(n + 1)  # 下标从 1 开始\n",
    "        pre = 1  # 上一个最小值的位置，初始为 1\n",
    "        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):\n",
    "            i += 1  # 下标从 1 开始\n",
    "            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            t.inc(i)  # 删除 i\n",
    "            pre = i\n",
    "        return ans\n",
    "\n",
    "# 树状数组模板\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        # 无重复元素nums：删除元素直至为空： 操作： 第一个元素为最小元素时，删除，否则移动到数组末尾\n",
    "        # 返回删除所有元素的最少操作次数\n",
    "\n",
    "        # 1. 暴力 超时\n",
    "        # ans = 0\n",
    "        # while nums:\n",
    "        #     if nums[0] == min(nums):\n",
    "        #         nums.pop(0)\n",
    "        #         ans += 1\n",
    "        #     else:\n",
    "        #         nums.append(nums[0])\n",
    "        #         nums.pop(0)\n",
    "        #         ans += 1\n",
    "        # return ans \n",
    "        \n",
    "        # 数组逆序对统计\n",
    "        # 2. 逆序对， 树状数组 n*log(n)\n",
    "        ans = n = len(nums)  # 先把 n 计入答案\n",
    "        t = BIT(n + 1)  # 下标从 1 开始\n",
    "        pre = 1  # 上一个最小值的位置，初始为 1\n",
    "        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):\n",
    "            i += 1  # 下标从 1 开始\n",
    "            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            t.inc(i)  # 删除 i\n",
    "            pre = i\n",
    "        return ans\n",
    "\n",
    "# 树状数组模板\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)  # 先把 n 计入答案\n",
    "        t = BIT(n + 1)  # 下标从 1 开始\n",
    "        pre = 1  # 上一个最小值的位置，初始为 1\n",
    "        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):\n",
    "            i += 1  # 下标从 1 开始\n",
    "            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            t.inc(i)  # 删除 i\n",
    "            pre = i\n",
    "        return ans\n",
    "\n",
    "# 树状数组模板\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 模拟过程\n",
    "        \"\"\"\n",
    "        先排序知道挨个删除的顺序，然后从最小的元素开始\n",
    "\n",
    "        被删除的元素位于中间，要先把前面的元素旋转到最后面，将被删除的元素暴露在开头\n",
    "        这个过程其实我们，保持一个指针，挪动它就好了。我们记录指针 pre 为上一个位置（上一次删除后自动诺位的下一人）\n",
    "\n",
    "        从第一个到第二个 pre->j，我知道两个下标的变化，删除j后，指针自动诺位到后面的元素j+1 变化应该是 pre -> j+1 (j-pre) \n",
    "        (j+1 可能需要旋转)\n",
    "        但随着删除运行到中间，也许 pre -> j+1 中间留下很多洞（已删除的元素）\n",
    "        需要越过他们 这需要记录/查询 [pre, j] 中间已经删除的个数\n",
    "\n",
    "        自动诺位后的pre 可能是之前被删除的元素，\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "        ans = n = len(nums) # ans先计入n, 代表至少n个删除\n",
    "        t = BIT(n+1)        # 输入是[0,n-1] 转换成 [1,n]\n",
    "\n",
    "        indices = sorted(range(n), key=lambda i:nums[i])\n",
    "        pre = 1\n",
    "        for i in indices:\n",
    "            # 下一个要删除的 indices i\n",
    "            # 有两个情况 [pre, i] or [i, pre]\n",
    "            i += 1 # i曾是nums下标，转化为 BIT 从1开始的下标\n",
    "            if pre <= i:\n",
    "                ans += i - pre - t.query(pre, i) # 查询 [pre, i] 中间有多少个删除\n",
    "            else: # 1 [i, pre] n 从pre到n再从1到i 但注意 i \n",
    "                ans += n - pre + i - t.query(pre, n) - t.query(1, i) \n",
    "            t.inc(i) \n",
    "            pre = i\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "class BIT:\n",
    "    # [1,n] ex [1,8]\n",
    "    # 不需要像前缀和ps数组保留0 index, 在sum数组中0 input没有lowbit res直接return 0\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0]*n  \n",
    "    \n",
    "    def inc(self, i: int) -> None:\n",
    "        # 给原数组i号元素递增1\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i #上溯至父节点\n",
    "\n",
    "    def sum(self, i: int) -> int:\n",
    "        # 计算 [0, i]\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            # i -= i & -i 去除一个lowbit, 下一行同样效果\n",
    "            i &= i - 1       \n",
    "        return res \n",
    "    \n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        # 查询 [left, right] 区间\n",
    "        return self.sum(right) - self.sum(left - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bittree = [0] * (n + 1)\n",
    "        # mark = [0] * (n + 1)\n",
    "        # mark[0] = 1\n",
    "        for i in range(n + 1):\n",
    "            t = i & (-i)\n",
    "            bittree[i] = t\n",
    "        def query(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans += bittree[x]\n",
    "                x -= x & (-x)\n",
    "            return ans\n",
    "        def update(x):\n",
    "            t = x\n",
    "            while x <= n:\n",
    "                bittree[x] -= 1\n",
    "                x += x & (-x)\n",
    "        d = list(range(1, n+1))\n",
    "        d.sort(key = lambda x: nums[x-1])\n",
    "        # print(d)\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for num in d:\n",
    "            if num >= pre:\n",
    "                ans = ans + query(num) - query(pre) \n",
    "            else:\n",
    "                ans = ans + query(n) - query(pre) + query(num) \n",
    "            update(num)\n",
    "            pre = num\n",
    "            # print(bittree)\n",
    "            # print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)  # 先把 n 计入答案\n",
    "        t = BIT(n + 1)  # 下标从 1 开始\n",
    "        pre = 1  # 上一个最小值的位置，初始为 1\n",
    "        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):\n",
    "            i += 1  # 下标从 1 开始\n",
    "            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre - t.query(pre, i)\n",
    "            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre + n - k + t.query(i, pre - 1)\n",
    "            t.inc(i)  # 删除 i\n",
    "            pre = i\n",
    "        return ans\n",
    "\n",
    "# 树状数组模板\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)  # 先把 n 计入答案\n",
    "        tree =[0]*(n + 1)  # 下标从 1 开始\n",
    "        pre = 1  # 上一个最小值的位置，初始为 1\n",
    "        def update(i: int) -> None:\n",
    "            while i <=n:\n",
    "                tree[i] += 1\n",
    "                i += i & -i\n",
    "\n",
    "        def ss(i: int) -> int:# 返回闭区间 [1, i] 的元素和\n",
    "            res = 0\n",
    "            while i > 0:\n",
    "                res +=tree[i]\n",
    "                i &= i - 1\n",
    "            return res\n",
    "        \n",
    "        def query(left: int, right: int) -> int:# 返回闭区间 [left, right] 的元素和\n",
    "            return ss(right) - ss(left - 1)\n",
    "        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):\n",
    "            i += 1  # 下标从 1 开始\n",
    "            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre - query(pre, i)\n",
    "            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数\n",
    "                ans += i - pre + n - k + query(i, pre - 1)\n",
    "            update(i)  # 删除 i\n",
    "            pre = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 树状数组模板\n",
    "# 维护中间被删除的数字个数\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree=[0]*n\n",
    "\n",
    "    def inc(self, i):\n",
    "        while i<len(self.tree):\n",
    "            self.tree[i]+=1\n",
    "            i+=i&(-i)\n",
    "    \n",
    "    def sum(self, i):\n",
    "        res=0\n",
    "        while i>0:\n",
    "            res+=self.tree[i]\n",
    "            i-=i&(-i)\n",
    "        return res\n",
    "    \n",
    "    def query(self, left, right):\n",
    "        return self.sum(right)-self.sum(left-1)\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        t=BIT(n+1)\n",
    "        ans=n\n",
    "        pre=1\n",
    "        ids=sorted(range(n),key=lambda i:nums[i])\n",
    "        for k,i in enumerate(ids):\n",
    "            i+=1\n",
    "            if pre<=i:\n",
    "                ans+=i-pre-t.query(pre, i)\n",
    "            else:\n",
    "                ans+= n-pre+i-(k-t.query(i, pre-1))\n",
    "            t.inc(i)\n",
    "            pre=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "            改为用一个下标来记录当前数组第一个数是谁\n",
    "            \n",
    "            删除一个数后，下标自动向右移动一位，（这次移动是免费的）\n",
    "\n",
    "            记录每个数的位置，从小到大删除。\n",
    "            上一个删除的数下标是 pre ，当前要删除的数下标是 i\n",
    "            从 pre 移动到i，需要移动多少次？\n",
    "                1. 维护中间被删除的数字个数\n",
    "                    树状数组。\n",
    "                     11=（1011） 二进制划分区间。区间的长度是2的幂\n",
    "                      [1,8] 8-1+1=8\n",
    "                      [9,10] 10-9+1=2\n",
    "                      [11.11] 11-11+1=1\n",
    "                    ——lowbit，不断加上 lowbit    i的父节点是i+i的lowbit\n",
    "                      9 = 1001          lowbit=1\n",
    "                       +1 1010  10      lowbit=2\n",
    "                       +2 1100  12      lowbit=4\n",
    "                       +4 10000 16\n",
    "\n",
    "                    如果 pre <= i: 移动次数为 i-pre-query(pre,i)\n",
    "                    如果 pre > i ： 先从pre移动到n，再移动到 i\n",
    "                                    n-pre-query(pre,n)  + i-query(1,i)\n",
    "                2. 脑筋急转弯\n",
    "\n",
    "        '''\n",
    "\n",
    "# 树状数组模版\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0]*n\n",
    "    \n",
    "    # 将下标 i 上的值加 1 \n",
    "    def inc(self,i:int) -> None:\n",
    "        while i<len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & (-i)\n",
    "\n",
    "    # 返回闭区间 [1, i]的元素和\n",
    "    def sum(self,i:int) -> int:\n",
    "        res = 0\n",
    "        while i>0:\n",
    "            res += self.tree[i]\n",
    "            i -= i & (-i)\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left,right]的元素和\n",
    "    def query(self,left:int,right:int) -> int:\n",
    "        return self.sum(right) - self.sum(left-1)\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        t = BIT(n+1)\n",
    "        pre = 1\n",
    "        ids = sorted(range(n),key=lambda i:nums[i])\n",
    "        for k,i in enumerate(ids,1):\n",
    "            i += 1\n",
    "            if pre<=i:\n",
    "                ans += i-pre-t.query(pre,i)\n",
    "            else :\n",
    "                ans +=  n-pre-t.query(pre,n)  + i-t.query(1,i)\n",
    "            t.inc(i)\n",
    "            pre=i\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        ans = n = len(nums)\n",
    "        id = sorted(range(n), key=lambda x: nums[x])\n",
    "        print(id)\n",
    "        for k in range(1,n):\n",
    "            pre=id[k-1]\n",
    "            i=id[k]\n",
    "            if i<pre:\n",
    "                ans+=n-k\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import pairwise\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=n\n",
    "        order=sorted(range(n),key=lambda x:nums[x])\n",
    "        print(order)\n",
    "        for k in range(1,n):\n",
    "            pre,now=order[k-1],order[k]\n",
    "            print(pre,now,k)\n",
    "            if now<pre:\n",
    "                ans+=n-k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums_idx = [(num, i) for i, num in enumerate(nums)]\n",
    "        nums_idx.sort()\n",
    "        sl = SortedList()\n",
    "        # print(nums_idx)\n",
    "        \n",
    "        cnt = 0\n",
    "        last_i = -1\n",
    "        for nu, i in nums_idx:\n",
    "            last_sl = sl.bisect_right(last_i)\n",
    "            i_sl = sl.bisect_left(i)\n",
    "            # print(i, sl, last_sl, i_sl)\n",
    "            if i > last_i:\n",
    "                cnt += i - last_i - i_sl + last_sl\n",
    "            else:\n",
    "                cnt += i + n - last_i - len(sl) + last_sl - i_sl\n",
    "            sl.add(i)\n",
    "            last_i = i\n",
    "            # print(i, cnt)\n",
    "        return cnt \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        res = n = len(nums)\n",
    "        arr = [(num, i) for i, num in enumerate(nums)]\n",
    "        arr.sort()\n",
    "        last = -1\n",
    "        for num, i in arr:\n",
    "            if i < last:\n",
    "                res += n - k\n",
    "            k += 1\n",
    "            last = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res, now = 0, 0\n",
    "        choose = []\n",
    "        sorted_nums = sorted([(e, i) for i, e in enumerate(nums)])\n",
    "        for e, i in sorted_nums:\n",
    "            if i >= now:\n",
    "                res += i-now+1 - bisect_left(choose, i) + bisect_left(choose, now)\n",
    "            else:\n",
    "                res += i+n-now+1 - len(choose) + bisect_left(choose, now) - bisect_left(choose, i)\n",
    "            now = i + 1 % n\n",
    "            insort(choose, i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nums): # init BIT\n",
    "        self.tree = [0] + nums\n",
    "        for i in range(1, len(self.tree)):\n",
    "            p = i + (i & -i) # index to parent\n",
    "            if p < len(self.tree):\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def add(self, i, k): # add k to index i\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += (i & -i) # add last set bit\n",
    "\n",
    "    def sum(self, i): # sum from index 1 to i\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= (i & -i) # minus the last set bit\n",
    "        return res\n",
    "\n",
    "    def query(self, l, r):\n",
    "        return self.sum(r) - self.sum(l - 1)\n",
    "# https://www.youtube.com/watch?v=13RA9fH-Dq4\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bit = BIT([1] * n)\n",
    "        idx_array = sorted([(v, i + 1) for i, v in enumerate(nums)])\n",
    "        last_pos = -1\n",
    "        res = n\n",
    "        for v, pos in idx_array:\n",
    "            if last_pos == -1:\n",
    "                res += bit.query(1, pos - 1)\n",
    "            elif pos > last_pos:\n",
    "                res += bit.query(last_pos + 1, pos - 1)\n",
    "            elif pos < last_pos:\n",
    "                res += bit.query(1, pos - 1) + bit.query(last_pos + 1, n)\n",
    "            bit.add(pos, -1)\n",
    "            last_pos = pos\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nums): # init BIT\n",
    "        self.tree = [0] + nums\n",
    "        for i in range(1, len(self.tree)):\n",
    "            p = i + (i & -i) # index to parent\n",
    "            if p < len(self.tree):\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def add(self, i, k): # add k to index i\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += (i & -i) # add last set bit\n",
    "\n",
    "    def sum(self, i): # sum from index 1 to i\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= (i & -i) # minus the last set bit\n",
    "        return res\n",
    "\n",
    "    def query(self, l, r):\n",
    "        return self.sum(r) - self.sum(l - 1)\n",
    "# https://www.youtube.com/watch?v=13RA9fH-Dq4\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bit = BIT([1] * n)\n",
    "        idx_array = sorted([(v, i + 1) for i, v in enumerate(nums)])\n",
    "        last_pos = -1\n",
    "        res = 0\n",
    "        for v, pos in idx_array:\n",
    "            if last_pos == -1:\n",
    "                res += bit.query(1, pos - 1)\n",
    "            elif pos > last_pos:\n",
    "                res += bit.query(last_pos + 1, pos - 1)\n",
    "            else:\n",
    "                res += bit.query(1, pos - 1) + bit.query(last_pos + 1, n)\n",
    "            bit.add(pos, -1)\n",
    "            last_pos = pos\n",
    "        return res + n\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nums): # init BIT\n",
    "        self.tree = [0] + nums\n",
    "        for i in range(1, len(self.tree)):\n",
    "            p = i + (i & -i) # index to parent\n",
    "            if p < len(self.tree):\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def add(self, i, k): # add k to index i\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += (i & -i) # add last set bit\n",
    "\n",
    "    def sum(self, i): # sum from index 1 to i\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= (i & -i) # minus the last set bit\n",
    "        return res\n",
    "\n",
    "    def query(self, l, r):\n",
    "        return self.sum(r) - self.sum(l - 1)\n",
    "# https://www.youtube.com/watch?v=13RA9fH-Dq4\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bit = BIT([1] * n)\n",
    "        idx_array = sorted([(v, i + 1) for i, v in enumerate(nums)])\n",
    "        last_pos = -1\n",
    "        res = 0\n",
    "        for v, pos in idx_array:\n",
    "            if last_pos == -1:\n",
    "                res += bit.query(1, pos - 1)\n",
    "            elif pos > last_pos:\n",
    "                res += bit.query(last_pos + 1, pos - 1)\n",
    "            elif pos < last_pos:\n",
    "                res += bit.query(1, pos - 1) + bit.query(last_pos + 1, n)\n",
    "            bit.add(pos, -1)\n",
    "            last_pos = pos\n",
    "        return res + n\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nums): # init BIT\n",
    "        self.tree = [0] + nums\n",
    "        for i in range(1, len(self.tree)):\n",
    "            p = i + (i & -i) # index to parent\n",
    "            if p < len(self.tree):\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def add(self, i, k): # add k to index i\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += (i & -i) # add last set bit\n",
    "\n",
    "    def sum(self, i): # sum from index 1 to i\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= (i & -i) # minus the last set bit\n",
    "        return res\n",
    "\n",
    "    def query(self, l, r):\n",
    "        return self.sum(r) - self.sum(l - 1)\n",
    "# https://www.youtube.com/watch?v=13RA9fH-Dq4\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bit = BIT([1] * n)\n",
    "        idx_array = sorted([(v, i + 1) for i, v in enumerate(nums)])\n",
    "        last_pos = -1\n",
    "        res = n\n",
    "        for v, pos in idx_array:\n",
    "            if last_pos == -1:\n",
    "                res += bit.query(1, pos - 1)\n",
    "            elif pos > last_pos:\n",
    "                res += bit.query(last_pos + 1, pos - 1)\n",
    "            elif pos < last_pos:\n",
    "                res += bit.query(1, pos - 1) + bit.query(last_pos + 1, n)\n",
    "            bit.add(pos, -1)\n",
    "            last_pos = pos\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# c = [0] * (n + 1)\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & (-x)\n",
    "\n",
    "def updateSum(i, k, c):\n",
    "    n = len(c) - 1\n",
    "    while i <= n:\n",
    "        c[i] += k\n",
    "        i += lowbit(i)\n",
    "\n",
    "def getSum(i, c):\n",
    "    res = 0\n",
    "    while i > 0:\n",
    "        res += c[i]\n",
    "        i -= lowbit(i)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        c = [0] * (n + 1)\n",
    "        arr = []\n",
    "        for i in range(n):\n",
    "            arr.append([nums[i], i])\n",
    "        arr.sort()\n",
    "        res = arr[0][1] + 1\n",
    "        updateSum(arr[0][1] + 1, 1, c)\n",
    "        for i in range(1, n):\n",
    "            currIdx = arr[i][1]\n",
    "            prevIdx = arr[i - 1][1]\n",
    "            if currIdx > prevIdx:\n",
    "                cnt = (currIdx - prevIdx) - (getSum(currIdx + 1, c) - getSum(prevIdx + 1, c))\n",
    "            else:\n",
    "                cnt = (n - 1 - prevIdx) - (getSum(n, c) - getSum(prevIdx + 1, c)) + (currIdx + 1 - getSum(currIdx + 1, c))\n",
    "            res += cnt\n",
    "            updateSum(currIdx + 1, 1, c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0] * n\n",
    "\n",
    "    def add(self, x, k):\n",
    "        while x < self.n:\n",
    "            self.c[x] += k\n",
    "            x += lowbit(x)\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.c[x]\n",
    "            x = x - lowbit(x)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        dx = [[d, i + 1] for i, d in enumerate(nums)]\n",
    "        dx.sort()\n",
    "        n = len(nums) + 1\n",
    "        t = BIT(n)\n",
    "        for i in range(1, n):\n",
    "            t.add(i, 1)\n",
    "\n",
    "        # for q in range(1, n):\n",
    "        #     ret = t.query(q)\n",
    "        #     print(ret)\n",
    "\n",
    "        i, ans = 0, 0\n",
    "        for d, j in dx:\n",
    "            if i < j:\n",
    "                ans += t.query(j) - t.query(i)\n",
    "            else:\n",
    "                ans += t.query(n-1) - t.query(i) + t.query(j)\n",
    "            t.add(j, -1)\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.trees = [0] * (n + 1)\n",
    "        \n",
    "    def update(self, pos, num):\n",
    "        while pos <= self.n:\n",
    "            self.trees[pos] += num\n",
    "            pos += pos & -pos\n",
    "            \n",
    "    def query(self, pos):\n",
    "        ans = 0\n",
    "        while pos > 0:\n",
    "            ans += self.trees[pos]\n",
    "            #pos -= pos & -pos\n",
    "            pos &= pos - 1\n",
    "        return ans\n",
    "    \n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        indexed_nums = sorted(zip(nums, range(n)), key = lambda x: x[0])\n",
    "        tree = BIT(n)\n",
    "        for i in range(n):\n",
    "            #print(i)\n",
    "            tree.update(i + 1, 1)\n",
    "        \n",
    "        relative_changes = [indexed_nums[0][1]]\n",
    "        total_cnt = n\n",
    "        for (num1, i), (num2, j) in pairwise(indexed_nums):\n",
    "            #print(i, num1, j, num2)\n",
    "            tree.update(i + 1, -1)\n",
    "            total_cnt -= 1\n",
    "            crt_change = 0\n",
    "            if i < j:\n",
    "                crt_change = tree.query(j + 1) - tree.query(i + 1) - 1\n",
    "            else:\n",
    "                crt_change = total_cnt - (tree.query(i + 1) - tree.query(j + 1) + 1)\n",
    "            print(crt_change)\n",
    "            relative_changes.append(crt_change)\n",
    "            \n",
    "        return sum(relative_changes) + n\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.trees = [0] * (n + 1)\n",
    "        \n",
    "    def update(self, pos, num):\n",
    "        while pos <= self.n:\n",
    "            self.trees[pos] += num\n",
    "            pos += pos & -pos\n",
    "            \n",
    "    def query(self, pos):\n",
    "        ans = 0\n",
    "        while pos > 0:\n",
    "            ans += self.trees[pos]\n",
    "            pos -= pos & -pos\n",
    "            #pos &= pos - 1\n",
    "        return ans\n",
    "    \n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        indexed_nums = sorted(zip(nums, range(n)), key = lambda x: x[0])\n",
    "        tree = BIT(n)\n",
    "        for i in range(n):\n",
    "            #print(i)\n",
    "            tree.update(i + 1, 1)\n",
    "        \n",
    "        relative_changes = [indexed_nums[0][1]]\n",
    "        total_cnt = n\n",
    "        for (num1, i), (num2, j) in pairwise(indexed_nums):\n",
    "            #print(i, num1, j, num2)\n",
    "            tree.update(i + 1, -1)\n",
    "            total_cnt -= 1\n",
    "            crt_change = 0\n",
    "            if i < j:\n",
    "                crt_change = tree.query(j + 1) - tree.query(i + 1) - 1\n",
    "            else:\n",
    "                crt_change = total_cnt - (tree.query(i + 1) - tree.query(j + 1) + 1)\n",
    "            print(crt_change)\n",
    "            relative_changes.append(crt_change)\n",
    "            \n",
    "        return sum(relative_changes) + n\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        raw_nums = [num for num in nums]\n",
    "        nums.sort(reverse=True)\n",
    "        print(raw_nums)\n",
    "        hash_dict = {}\n",
    "        for i in range(len(nums)):\n",
    "            hash_dict[nums[i]] = i+1\n",
    "        new_num = []\n",
    "        for num in raw_nums:\n",
    "            new_num.append(hash_dict[num])\n",
    "        s = new_num + new_num\n",
    "        tree_array = [0 for _ in range(len(raw_nums) + 1)]\n",
    "\n",
    "        def lowbit(x):\n",
    "            return x&-x\n",
    "\n",
    "        def add(x, c):\n",
    "            while x < len(tree_array):\n",
    "                tree_array[x] += c\n",
    "                x += lowbit(x)\n",
    "        \n",
    "        def sum_tree(x):\n",
    "            total = 0\n",
    "            while x:\n",
    "                total += tree_array[x]\n",
    "                x -= lowbit(x)\n",
    "            return total \n",
    "        nxd_arr = [0 for _ in range(len(raw_nums)+1)]\n",
    "        op_num = 0\n",
    "        for i in range(len(s)):\n",
    "            tp = sum_tree(s[i]-1)\n",
    "            if i >= len(s)//2:\n",
    "                if s[i] + 1 < len(nxd_arr):\n",
    "                    op_num += tp - nxd_arr[s[i]+1] + 1\n",
    "                else:\n",
    "                    op_num += i - len(s)//2\n",
    "            nxd_arr[s[i]] = tp\n",
    "            add(s[i],1)\n",
    "\n",
    "        return op_num + len(raw_nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        raw_nums = [num for num in nums]\n",
    "        nums.sort(reverse=True)\n",
    "        print(raw_nums)\n",
    "        hash_dict = {}\n",
    "        for i in range(len(nums)):\n",
    "            hash_dict[nums[i]] = i+1\n",
    "        new_num = []\n",
    "        for num in raw_nums:\n",
    "            new_num.append(hash_dict[num])\n",
    "        s = new_num + new_num\n",
    "        tree_array = [0 for _ in range(len(raw_nums) + 1)]\n",
    "\n",
    "        def lowbit(x):\n",
    "            return x&-x\n",
    "\n",
    "        def add(x, c):\n",
    "            while x < len(tree_array):\n",
    "                tree_array[x] += c\n",
    "                x += lowbit(x)\n",
    "        \n",
    "        def sum_tree(x):\n",
    "            total = 0\n",
    "            while x:\n",
    "                total += tree_array[x]\n",
    "                x -= lowbit(x)\n",
    "            return total \n",
    "        nxd_arr = [0 for _ in range(len(raw_nums)+1)]\n",
    "        op_num = 0\n",
    "        for i in range(len(s)):\n",
    "            tp = sum_tree(s[i]-1)\n",
    "            if i >= len(s)//2:\n",
    "                if s[i] + 1 < len(nxd_arr):\n",
    "                    op_num += tp - nxd_arr[s[i]+1] + 1\n",
    "                else:\n",
    "                    op_num += i - len(s)//2\n",
    "            nxd_arr[s[i]] = tp\n",
    "            add(s[i],1)\n",
    "\n",
    "        return op_num + len(raw_nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOperationsToEmptyArray(self, nums: List[int]) -> int:\n",
    "        tmp={}\n",
    "        for i,num in enumerate(nums):\n",
    "            tmp[num]=i\n",
    "        pos=[t[1] for t in sorted(tmp.items())]\n",
    "        ans=len(nums)\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            if pos[i+1]<pos[i]:\n",
    "                ans+=len(nums)-i-1\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
